1. Field of the Invention
The present invention relates to a content addressable memory, and particularly to a construction for reducing current consumption and a peak current in a search operation and for speeding up the search operation.
2. Description of the Background Art
A CAM (Content Addressable Memory) has, in addition to a function of reading/writing data, a function of determining matching of stored data with supplied search data. One entry storing a search data word is configured by a plurality of CAM cells, and stores word bits of a search candidate. Each entry is provided with a match line coupled to corresponding CAM cells in parallel. When a search data word matches a stored data word, a corresponding match line is kept at a state of “1”. When mismatch occurs, the corresponding match line is driven to a state of “0”.
By determining the voltage level of the match line, it is possible to determine whether the data corresponding to the search data is stored, e.g., in a table. This type of content addressable memory is used for determining cache-miss/hit in a cache memory and a router for communications application. A network router or the like performs routing of an IP packet through comparison of an IP address stored in a content addressable memory provided in the router with an externally supplied IP address. For example, a value indicating a next destination address is written into an IP packet based on match line information of the matching state in the content addressable memory in the router, and then the IP packet is delivered from a corresponding port.
Usually, in the CAM used in the communications router or the like, search data has a bit width from 72 bits to 288 bits, and the number of the entries is about 64 K.
In a conventional CAM, the match lines are precharged to a power supply voltage VDD (or a ground voltage GND level) during a precharge period. During a search period for detecting matching between the stored data and the search data, the search data is compared with data bits of entry CAM cells. When mismatch occurs, transistors in the CAM cells discharge (or charge) the corresponding match line to the ground voltage (or power supply voltage level) different from the precharge voltage. Therefore, when n CAM cells are in the mismatch state in one entry, a current of (I_miss×n) is discharged (or charged) through one match line, where I_miss represents a current driven by one CAM cell in the mismatch state. When the match occurs in all the data bits of the CAM cells in the entry, no discharge (or charge) path is present in the CAM cells. Therefore, the match line in the match state is kept at the level of the precharge voltage of power supply voltage VDD or ground voltage GND.
In the CAM, the search data is supplied in parallel to the plurality of entries, and the search operations are executed in parallel in the respective entries. Search line transmitting the search data and the match line producing a signal indicative of a match result are precharged to predetermined voltage levels in each search cycle of performing the search operation. As an example, the search line is precharged to the ground voltage level, and the match line is precharged to the power supply voltage level. The search line is coupled to the CAM cells in all entries. Therefore, the search line has a large capacitive load. A majority of the match lines except the line exhibiting the match state in the search operation change between the power supply voltage level and the ground voltage level in each search cycle. Therefore, the charge and discharge currents of the search line and the match line are large, resulting in a problem that current dissipation and power consumption are large.
An article 1 (H. Noda, et al., “A Cost-Efficient High-Performance Dynamic TCAM With Pipelined Hierarchical Searching and Shift Redundancy Architecture”, IEEE JSSC, Vol. 40, No. 1, January 2005, pp. 245-253) has disclosed a construction for reducing current consumption of a content addressable memory and achieving a fast search operation. In the construction disclosed in the article 1, the match line has a hierarchical configuration. A plurality of local match lines are arranged for one entry. These plurality of local match lines are commonly coupled to a global match line. Searching operation is performed for each local match line in a pipelined fashion. For example, search data of 144 bits is divided into 72-bit data. On the local match line of the block in which no matching occurs in first 72 bits, it is no longer necessary to perform the subsequent search. Therefore, in the entries corresponding to the mismatch block, the search line is not activated in the next stage, and the local match lines are not discharged. The number of the local match lines to be charged and discharged can be reduced, and the power consumption can be reduced.
In the article 1, a DRAM-type cell construction is employed for storing search data, and each DRAM cell stores a data bit, to store ternary data. The CAM cell storing the ternary data is generally referred to as a TCAM (Ternary CAM) cell, and can store a “don't care” state.
A publication 1 (Japanese Patent Laying-Open No. 10-027481) has disclosed a construction aiming to achieve a fast search operation. In the construction disclosed in the publication 1, a match line is precharged to a ground voltage level during standby. In a search operation, each match line is supplied with a current of a magnitude substantially equal to that flowing when one-bit mismatch occurs with respect to the search data. Voltage rising of the match line in the mismatch entry is suppressed to or below a reference voltage for reducing the current consumption.
A publication 2 (Japanese Patent Laying-Open No. 2004-192695) has likewise disclosed a construction aiming to reduce the current consumption in a search operation. In the publication 2, complementary search lines are short-circuited to precharge the search lines to an intermediate voltage level during standby. A match line is precharged to the ground voltage level during standby, and is charged up by accumulated charges supplied from a capacitance element when the search operation starts. A capacitive division by the capacitance element and the match line sets an upper limit of the voltage level of the match line to an intermediate voltage level lower than the power supply voltage. A buffer circuit is employed for sensing the voltage level of the match line.
A publication (Japanese Patent Laying-Open No. 2003-100086) has disclosed a construction for executing a fast search operation even when a match line load is large. In the publication 3, a reference voltage generating circuit and a differential amplifier circuit are arranged for each match line. The differential amplifier circuit compares a reference voltage with a match line voltage for increasing a speed of a search and determination operation.
A publication 4 (Japanese Patent Laying-Open No. 2002-358791) has disclosed a construction for reducing a precharge current in a search operation. In the publication 4, CAM entries are divided. For the divided CAM entries, precharge voltages and the drive voltage of the match line in the miss state are set oppositely. Specifically, on one divided entry, the match line is precharged to an H level (logical higH level), and is set to an L level (logical low level) in the mismatch. On another divided entry, the match line is precharged to the L level, and is set to the H level in the mismatch. By short-circuiting the match lines in the divided CAM entries, redistribution of electric charges occurs in the mismatch entry during precharging, and the divided match lines therein are driven to an intermediate voltage, so that the current consumption is reduced.
A publication 5 (Japanese Patent Laying-Open No. 2002-245783) has also disclosed a construction for reducing current consumption in a search operation. In the construction disclosed in the publication 5, a dummy match line is provided to have the same capacitance as an entry in a match state. A match line and the dummy match line are precharged to a ground voltage, and are supplied with a current in a search operation. When the dummy match line is determined to be at the voltage level of an H level, a determination timing signal is produced to stop charging of the match line. Current consumption is reduced by reducing a period for supplying the current to the match line. A differential amplifier circuit is used for determining the voltage level of the match line, and compares a reference voltage with the match line voltage.
A publication 6 (Japanese Patent Laying-Open No. 2001-319481) has disclosed a construction for reducing current consumption in a search operation and for increasing a speed of the search operation. In the construction disclosed in the publication 6, a bit line for writing/reading data is provided separately from a search line for transferring search data. The bit line is precharged to the H level, and the search line is precharged to the L level. In a search operation, the search and bit lines are short-circuited according to the search data so that the search line at a high level is set to an intermediate voltage level, and an amplitude of a search line voltage is set to be between the ground voltage and the intermediate voltage level. The match line is precharged to the intermediate voltage level, and is charged up via a decouple transistor in the search operation. Via such decouple transistor, the match line is coupled to a sense amplifier. Even when a sense node of input nodes of the sense amplifier is charged, the decouple transistor suppresses voltage rising of the match line. Upon mismatch, the sense node is discharged via the match line. The voltage amplitude(s) of the match line and/or search line is (are) restricted, so that the current consumption is reduced, and the search operation is speeded up.
In the CAM and TCAM, as described above, the search line and the match line are charged and discharged in each search cycle, and the current consumption is large. In the article 1 described above, the match line has a hierarchical configuration, and the search operation is performed in a pipelined fashion for each of the plurality of local match line blocks. For the entry of the mismatching in a certain pipeline stage (local match line block), the subsequent discharging of the search line and the local match line is not performed for reducing the current consumption.
In the article 1, the match line has the hierarchical configuration, but the search line is arranged commonly to all the entries. Therefore, the search line of a large load capacitance is charged and discharged between the power supply voltage level and the ground voltage level according to the search data, and there is a room for improvement in reducing the current consumption.
The search operation is performed concurrently on many search and local match lines. Therefore, a simultaneous operation current (peak current) is large, which may cause switching noises.
In the article 1, the global and local match lines are charged and discharged between the levels of the power supply voltage and the ground voltage. Therefore, signal amplitudes of the local and global match lines indicating a result of the match-detection are large, and such a problem arises that there is a limit in reduction of the current consumption and the reduction of the time required until settlement of the match result. The power supply voltage may be lowered to reduce the signal amplitude. In this case, however, the operation speed of the transistor element determines the lower limit of the power supply voltage level, to pose the restriction on the increase in operation speed.
In the construction disclosed in the publication 1, a transistor similar to the CAM cell is used to produce and supply a current of one-bit miss state to the match line. The transistor receiving a reference voltage on its gate is used for charging the match line, to suppress the voltage level increase of the match line in the mismatch, at or below the reference voltage. However, such a problem occurs that the match line in the match state is charged to the power supply voltage level, and the voltage amplitude thereof becomes large. The publication 1 has not disclosed a construction for setting the voltage amplitude of the match line to or below an intermediate voltage level regardless of the match and mismatch states. Also, no consideration is given to an influence that is exerted on the match line precharging current by an off-leakage current flowing via the CAM cells in the match state of an entry.
In the construction disclosed in the publication 2, by the charge redistribution performed by the capacitance division by the match line and a capacitance element, the precharge voltage level of the match line is set. Therefore, the capacitance values must be adjusted between the match line and the capacitance element with high precision, and it is difficult to charge up precisely the match line in the match state to a desired intermediate voltage level. In the publication 2, the search line is precharged by short-circuiting the complementary search lines for reducing the charge/discharge currents of the search lines. However, no consideration is given to reduction of the capacitance of the search line. Accordingly, the search line is charged from the intermediate voltage level to the power supply voltage level according to the search data, and such problem arises that as the number of entries increases, the load capacitance accordingly increases and the current consumption cannot be reduced.
In the construction disclosed in the publication 3, the reference voltage generating circuit and the differential amplifier circuit are arranged for each match line. In this publication 3, however, the match line is precharged to the power supply voltage level. Therefore, the voltage amplitude of the match line is large, resulting in a problem that the fast search operation and the reduced current consumption cannot be achieved.
In the construction disclosed in the publication 4, the CAM entry is divided and such a problem arises that the divided entries are precharged to different voltage levels, and it is difficult to achieve a uniform operation speed between the divided entries. In each entry, it is necessary to control the connection of the match line in the divided entry according to the match/mismatch of the divided entries, and a circuit for such connection requires a large occupation area. Further, the match line of each divided entry has the voltage amplitude of the power supply voltage level, so that the fast search operation cannot be achieved. When the number of bits of the search data increases and accordingly the number of bits of the CAM cells of the entry increases, the load of the match line increases to increase the current consumption for precharging from the intermediate voltage level to the power supply voltage level.
In the construction disclosed in the publication 5, the determination timing is set by detecting the voltage level of the dummy match line, and thereby the precharge period of the match line is adjusted. However, no consideration is given to the restriction of the precharge current value. Also, the charging of the match line in the match state is not stopped, and the current consumption in the search operation can be reduced to a limited extent.
In the construction disclosed in the publication 6, the search line and the bit line are short-circuited to set the voltage amplitude of the search line to the intermediate voltage smaller than the power supply voltage. Therefore, the bit line must be precharged to the power supply voltage level, resulting in a problem that the current consumption cannot be reduced. The match line is coupled to the buffer (sense amplifier) via the decouple transistor for charging up the match line in the match state to the intermediate voltage level and for pulling up the sense node to the power supply voltage level. Accordingly, the discharge speed of the sense node slows in the state of one-bit miss for the search data, resulting in a problem that the search operation cannot be performed fast. The publication 6 discloses another embodiment, in which redistribution of the accumulated charges of the capacitance element sets the voltage level of the match line in the match state. This scheme results in a problem that adjustment of the load capacitances of the capacitance element and the match line cannot be made easily, similarly to the publication 2.